package interview.Sorting;

public class MergeSort {
	private static void divide(int [] num, int start, int end){
		if(end==start) return;
		if(end-start==1){
			if(num[start]>num[end])
				Generic.swap(num,start,end);
			return;
		}
		int mid=start+(end-start)/2;
		divide(num,start,mid);
		divide(num,mid+1,end);
		conquer(num,start,end);
	}
	private static void conquer(int[] num, int start, int end) {
		int[] copy = new int[end-start+1];
		int i,j,k=0;
		i = start;
		int mid = start+ ((end-start)/2);
		j = mid+1;
		while((i<=mid)&&(j<=end)){
			if(num[i]<num[j])
				copy[k++]=num[i++];
			else
				copy[k++]=num[j++];
		}
		if(i>mid)
			while(j<=end)
				copy[k++]=num[j++];
		else
			while(i<=mid)
				copy[k++]=num[i++];
		
		for(i=0;i<k;i++)
			num[start++]=copy[i];
		System.out.println();
		Generic.printArray(num);
	}
	public static void sort (int num[]){
		divide(num,0, num.length-1);
	}
}
